NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part2/12531

Internet Message Format | 1996-08-05 | 3.5 KB

Path: keats.ugrad.cs.ubc.ca!not-for-mail
From: [e-mail] (Kazimir Kylheku)
Newsgroups: comp.lang.c
Subject: Re: How can I use huge || very small number?
Date: 1 Apr 1996 07:29:44 -0800
Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
Message-ID: <[e-mail]>
References: <[e-mail]> <4joh0l$[e-mail]> <4joijj$[e-mail]> <4joj2c$[e-mail]>
NNTP-Posting-Host: keats.ugrad.cs.ubc.ca

In article <4joj2c$[e-mail]>,
Usman Muzaffar <[e-mail]> wrote:
 >In article <4joijj$[e-mail]>,
 >Justin C Lloyd <[e-mail]> wrote:
 >>On 1 Apr 1996 12:08:53 GMT, Usman Muzaffar ([e-mail])
 >>wrote:
 >>** In article <[e-mail]>,
 >>** whoever  <[e-mail]> wrote:
 >>** >may be it is FAQ but...
 >>** >how can I compute 10000! or 0.12345......
 >>
 >>** 10000! is a very, very big number.
 >>** I'm not sure it's even representable by standard IEEE fp notation.
 >>** Any have that formula? 2*pi*e something or another.
 >>
 >>
 >>I'm sorry that I don't remember the location (possibly sunsite.unc.edu?),
 >>but there was a collection of C snippets/programs that contained a program
 >>that "calculated" huge factorials by using strings.  I don't recall the
 >>algorithm, it was quite complicated.  Anyone else know what I'm referring
 >>to?
 >>
 >
 >If it's what I'm thinking of, it's not complicated at all.
 >Essentially, you teach the computer to do math the way we do, never doing
 >more than one digit at a time, and just writing lines and lines of numerals
 >in neat rows. The advantage is in output: it's not that you couldn't write
 >a bit of code that couldn't calculate 10000!, but getting it from binary
 >to decimal output is as cumbersome as calculating the value itself.
 >
 >Of course, the down side is that it's very slow, inelegant, and (let's face it)
 >kind of stupid to get a computer to add the way we do. After all, it's the
 >very fact that they *don't* do things slowly is what first attracted us. :)

Actually the way computers add numbers is very much like ``the way we do it'',
with some refinements (such as lookahead carry propagation to do more work in
parallel). Multiplication is also done similarly, with all kinds of refinements
to improve the use of parallel computation.

The nice thing is that in binary, the rules for addition simply boil down to
logical operations. The possibilities for adding two binary digits and a carry
are easily enumerated by logic, and implemented using logic gates.

The way primitive operations in multi-precision integer math libraries are
implemented essentially mimics the way people do addition, multiplication or
division. It's not stupid at all. If you want to do math with large integers,
you have to implement these primitive operations. It is slower, but that's just
the rule of TANSTAAFL at work.

The way you would implement an arithmetic operation on a large integer would
not precisely mimic what you do on paper, of course. And you do not have to
deal with one digit at a time. You deal with entire words at a time. For
example, if your computer handles 16-bit words efficiently, you represent the
large integers as arrays if 16-bit words, and do the computations in base
65536 rather than base 10, but the basics are still the same. You start with
the rightmost words, add them, carry the 1 or 0, add the next ones with the
carry, etc.


--